In order to realize computational capacity extending beyond conventional computer limits, research on quantum computation has become active in recent years. For example, the use of the algorithm disclosed by P. W. Shor at the 35th Annual Symposium of the Foundations of Computer Science in 1995 achieves the factorization of a large integer into prime factors in time expressed by a polynomial indicating the number of bits.
In conventional computers, execution time increases as an exponential function of the number of bits. In the conventional computers, execution time proportional to the number of bits is required to retrieve an N-bit database. Using the algorithm proposed by L. Grover, Physical Review Letters, Vol. 79, p. 325, 1997, however, the database can be retrieved in time proportional to the square root of N.
The above quantum computation is realized using a fundamental unit called a quantum bit (qubit) substituting for a classical bit. The qubit is characterized by including a linear superposition of a state |0> corresponding to a logical value 0 and a state |1> corresponding to a logical value 1, i.e., |Ψ>=a|0>+b|1>(a2+b2=1). Further, quantum gates for performing a unitary transform of |Ψ>→U|Ψ> to one qubit, controlled-unitary transform gates for performing the unitary transform to another qubit depending on the state of the one qubit, and a quantum circuit composed of the above gates are needed.
The above-mentioned content will now be described using Shor's algorithm to resolve an integer N into prime factors as an example.
This algorithm is implemented using the combination of conventional computation (classical computation) and quantum computation.
1. When N is an even number, 2 is output as a factor.
2. Whether p and q satisfying conditions that p≧1, q≧2, and N=pq exist is determined by classical computation. If they exist, p is output as a factor.
3. Select an integer a (1<a<N) at random. The greatest common divisor of a and N is calculated using Euclidean algorithm. When the greatest common divisor is larger than 1, the greatest common divisor is output.
4. Order r of a modN is computed using a quantum computer for finding order.
5. When r is an odd number or an even number, which satisfies that ar/2=−1(modN), the routine is returned to step 3. In other cases, the greatest common divisor of ar/2−1 and N and the greatest common divisor of ar/2+1 and N are computed. When these greatest common divisors are not self-evident factors (1 or N), they are output.
The quantum computer used in step 4 is realized by a quantum circuit shown in FIG. 1. In this case, the number of bits is 4. The quantum circuit shown in FIG. 1 includes a circuit 21 for applying a phase depending on order and an inverse Fourier transform circuit 22 for obtaining the order from the phase. A controlled-unitary transform gate Ua 23 in the circuit 21 for applying the phase depending on the order is given bycUa|0>|x>=|0>|x>, cUa|1>|x>=|1>|ax modN>,  (1)where c denotes a constant. In this circuit, a qubit is transformed as
                                                                                                              cU                    a                                    ⁡                                      (                                                                                          0                        〉                                            +                                                                      1                        〉                                                              )                                                  ⁢                                                    1                  〉                                            =                                                ∑                                      j                    =                    0                                                  ⁢                                                      ∑                                          s                      =                      0                                                              r                      -                      1                                                        ⁢                                                            exp                      ⁡                                              [                                                                              2                            n                                                    ⁢                          πⅈ                          ⁢                                                                                                          ⁢                                                      sj                            /                            r                                                                          ]                                                              ⁢                    j                                                                        〉                    ⁢                                                u              s                        〉                          ,                            (        2        )            where |us> is defined by
                                                    u            s                    〉                =                              1                          r                                ⁢                                    ∑                              k                =                0                                            r                -                1                                      ⁢                                          exp                ⁡                                  [                                                            -                      2                                        ⁢                    πⅈ                    ⁢                                                                                  ⁢                                          sk                      /                      r                                                        ]                                            ⁢                                                                                                            a                      k                                        ⁢                                                                                  ⁢                    mod                    ⁢                                                                                  ⁢                    N                                    〉                                .                                                                        (        3        )            When a first qubit is subjected to an inverse Fourier transform, the following expression is obtained.
                              1                      r                          ⁢                                        s            /            r                    〉                ⁢                                        u            s                    〉                                    (        4        )            When the first qubit is measured, s/r is obtained, so that the estimate of r can be obtained. Each Hadamard gate 24 performs the transform expressed as
                                                      0            〉                    ↔                                    1                              2                                      ⁢                          (                                                                  0                  〉                                +                                                    1                  〉                                            )                                      ⁢                                  ⁢                                          1            〉                    ↔                                    1                              2                                      ⁢                                          (                                                                          0                    〉                                    -                                                          1                    〉                                                  )                            .                                                          (        5        )            
In addition, the inverse Fourier transform uses controlled-rotation gates 25 each performing a kind of controlled-unitary transform. Each controlled-rotation gate 25 is given by
                              R          k                ⁢                  :                ⁢                  {                                                                                                                                      0                      〉                                        ⁢                                                                0                      〉                                                        ->                                                                                  0                      〉                                        ⁢                                                                0                      〉                                                                                                                                                                                                            0                      〉                                        ⁢                                                                1                      〉                                                        ->                                                                                  0                      〉                                        ⁢                                                                1                      〉                                                                                                                                                                                                            1                      〉                                        ⁢                                                                0                      〉                                                        ->                                                                                  1                      〉                                        ⁢                                                                0                      〉                                                                                                                                                                                                                                                                  1                          〉                                                ⁢                                                                            1                          〉                                                                    ->                                                                        exp                          ⁢                                                                                                          [                                                                                    2                                                              -                                k                                                                                      ⁢                            πⅈ                                                    ]                                                ⁢                        1                                                              〉                                    ⁢                                                                                  1                      〉                                        .                                                                                                          (        6        )            
To realize Shor's algorithm, a nuclear magnetic resonance (NMR) technology using spin nuclei in an organic molecule as quantum bits has been utilized.
Recently, an experiment in factoring 15=3×5 into prime factors has been reported by L. M. K. Vandersypen, M. Steffen, G. Breyta, C. S. Yannonl, M. H. Sherwood, and I. L. Chuang, Nature, Vol. 414, p. 883, 2001.